/*
 * @lc app=leetcode.cn id=51 lang=java
 *
 * [51] N 皇后
 */

// @lc code=start

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<>();

        int[] arr = new int[n]; // arr[i] = j 表示第i行的皇后在第j列

        dfs(res, 0, n, arr);

        return res;
    }

    private void dfs(List<List<String>> res, int n, int max, int[] arr) {
        if(n == max) {
            addResult(res, arr);
            return;
        }

        for(int i = 0; i < max; i++) {
            // 首先将皇后摆在当前行的第一列 （i从0开始）
            arr[n] = i;
            // 如果与前面的皇后不冲突，则摆放下一个皇后
            if (judge(n, arr))
                dfs(res, n + 1, max, arr);
            //冲突，则向后挪一列
        }
    }


    public boolean judge(int n, int[] arr) {
        for (int i = 0; i < n; i++) {
            if (arr[i] == arr[n] || Math.abs(n - i) == Math.abs(arr[i] - arr[n]))
                return false;
        }
        return true;
    }


    private void addResult(List<List<String>> result, int[] arr) {
        List<String> list = new ArrayList<>();
        // 将整数数组结果转为题目要求的结果
        for (int i = 0; i < arr.length; i++) {
            // 每一行的皇后存放结果
            char[] chars = new char[arr.length];
            for (int j = 0; j < arr.length; j++) {
                chars[j] = '.';
            }
            // 整数数组的值即皇后所在的列，只需要将字符数组的列下标改为Q即可
            chars[arr[i]] = 'Q';
            list.add(String.valueOf(chars));
        }
        result.add(list);
    }
}
// @lc code=end

